9023. Minimum increments

Given array with n positive integers. Find the minimum number of operations required so that an Arithmetic Progression with the array elements is achieved with common difference as 1. In a single operation, any element can be incremented by 1.

Input. First line contains number n (n ≤ 10⁶). Second line contains n positive integers, each is no more than 10⁶.

Output. Print the minimum number of operations to get an Arithmetic Progression with common difference as 1.

Explanation. In the first test array should be converted to 8 9 10 11 12. In this case we’ll make (8 – 3) + (9 – 6) + (10 – 4) + (11 – 11) + (12 – 5) = 5 + 3 + 6 + 0 + 7 = 21 operations.

Sample input 1	Sample output 1
5 3 6 4 11 5	21
Sample input 2	Sample output 2
5 4 4 5 5 7	5

РЕШЕНИЕ

binary search

Algorithm analysis

Let the required least number of operations transform the original array m[0], m[1], …, m[n – 1] into x, x + 1, x + 2, …, x + n – 1. Obviously, that m[0] ≤ x ≤ max(m[0], m[1], …, m[n – 1]).

A sequence d = [x, x + 1, x + 2, …, x + n – 1] is called suitable if array m can be transformed into array d (for this, m[i] ≤ d[i] must hold for all i from 0 up to n – 1). It remains to find the smallest value of x for which the sequence d will be suitable. This can be done with a binary search.

Example

Consider the first test case. Let d = [x, x + 1, x + 2, …, x + n – 1] be an appropriate sequence with the minimum sum of elements. Obviously, m[0] = 3 ≤ x ≤ 11 = max(m[i]). Using binary search, we look for the smallest x for which the sequence d is suitable.

For example, for x = 6 the sequence d will not be suitable, but for x = 8 it will.

Consider the second test. Start the binary search on the interval 4 ≤ x ≤ 7. For example, for x = 4, the sequence d is already suitable.

Algorithm realization

The input sequence is stored in array m. The sequence x, x + 1, x + 2, …, x + n – 1 is stored in array d.

#define MAX 1000000

int m[MAX], d[MAX];

Function check in array d generates a sequence first, first + 1, first + 2, …, first + n – 1. If for each i (0 ≤ i ≤ n – 1) an inequality m[i] ≤ d[i] holds, then array d can be obtained from m by increasing the elements by 1, and in this case, we will call the array d to be suitable. If array d is suitable, then check function returns 1, otherwise it returns 0.

int check(int first)

{

for (int i = 0; i < n; i++)

d[i] = first++;

for (int i = 0; i < n; i++)

if (m[i] > d[i]) return 0;

return 1;

}

The main part of the program. Read the input value n. Compute the maximum value mx in array m.

scanf("%d", &n);

mx = 0;

for (i = 0; i < n; i++)

{

scanf("%d", &m[i]);

if (m[i] > mx) mx = m[i];

}

start = m[0];

end = mx;

Start a binary search for the x value in the interval [start; end] = [m[0]; mx]. We are looking for the minimum value of x for which the sequence x, x + 1, x + 2, …, x + n – 1 can be obtained from m[0], m[1], …, m[n – 1].

while (start < end)

{

mid = (start + end) / 2;

if (check(mid))

end = mid;

else

start = mid + 1;

}

Generate the required arithmetic progression.

for (i = 0; i < n; i++)

d[i] = start++;

Find the number of operations for which you can get the progression.

op = 0;

for (int i = 0; i < n; i++)

op += (d[i] - m[i]);

Print the answer.

printf("%lld\n", op);